package org.czl.leetCode1;

public class L1373 {

      public class TreeNode {
          int val;
         TreeNode left;
         TreeNode right;
          TreeNode() {}
          TreeNode(int val) { this.val = val; }
          TreeNode(int val, TreeNode left, TreeNode right) {
              this.val = val;
              this.left = left;
              this.right = right;
          }
      }

    class Solution {

        class Info {
            boolean isBST;
            int minValue;
            int maxValue;
            int sum;
            int ans;
            Info(boolean isBST, int minValue, int maxValue, int sumValue, int ans) {
                this.isBST = isBST;
                this.minValue = minValue;
                this.maxValue = maxValue;
                this.sum = sumValue;
                this.ans = ans;
            }
        }

        public int maxSumBST(TreeNode root) {
            return dfs(root).ans;
        }

        Info dfs(TreeNode root){
            if(root == null){
                return new Info(true, Integer.MAX_VALUE, Integer.MIN_VALUE, 0, 0);
            }
            Info left = dfs(root.left);
            Info right = dfs(root.right);
            //不要当前节点
            int minValue = Math.min(Math.min(left.minValue, right.minValue), root.val);
            int maxValue = Math.max(Math.max(left.maxValue, right.maxValue), root.val);
            int sum = left.sum + right.sum + root.val;
            int ans = Math.max(right.ans, left.ans);
            boolean flag = left.isBST && right.isBST && root.val > left.maxValue && root.val < right.minValue;
            if(flag){
                ans = Math.max(ans, sum);
            }
            return new Info(flag, minValue, maxValue, sum, ans);
        }
    }
}
